Bitmap represents a compressed bitmap where you can add integers. Add the integer x to the bitmap AddInt adds the integer x to the bitmap (convenience method: the parameter is casted to uint32 and we call Add) AddMany add all of the values in dat AddRange adds the integers in [rangeStart, rangeEnd) to the bitmap.
The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range
while uint64(0x100000000) cannot be represented as a 32-bit value. And computes the intersection between two bitmaps and stores the result in the current bitmap AndAny provides a result equivalent to x1.And(FastOr(bitmaps)).
It's optimized to minimize allocations. It also might be faster than separate calls. AndCardinality returns the cardinality of the intersection between two bitmaps, bitmaps are not modified AndNot computes the difference between two bitmaps and stores the result in the current bitmap CheckedAdd adds the integer x to the bitmap and return true if it was added (false if the integer was already present) CheckedRemove removes the integer x from the bitmap and return true if the integer was effectively removed (and false if the integer was not present) Checksum computes a hash (currently FNV-1a) for a bitmap that is suitable for
using bitmaps as elements in hash sets or as keys in hash maps, as well as
generally quicker comparisons.
The implementation is biased towards efficiency in little endian machines, so
expect some extra CPU cycles and memory to be used if your machine is big endian.
Likewise, do not use this to verify integrity unless you are certain you will load
the bitmap on a machine with the same endianess used to create it. (Thankfully
very few people use big endian machines these days.) Clear resets the Bitmap to be logically empty, but may retain
some memory allocations that may speed up future operations Clone creates a copy of the Bitmap CloneCopyOnWriteContainers clones all containers which have
needCopyOnWrite set to true.
This can be used to make sure it is safe to munmap a []byte
that the roaring array may still have a reference to, after
calling FromBuffer.
More generally this function is useful if you call FromBuffer
to construct a bitmap with a backing array buf
and then later discard the buf array. Note that you should call
CloneCopyOnWriteContainers on all bitmaps that were derived
from the 'FromBuffer' bitmap since they map have dependencies
on the buf array as well. Contains returns true if the integer is contained in the bitmap ContainsInt returns true if the integer is contained in the bitmap (this is a convenience method, the parameter is casted to uint32 and Contains is called) DenseSize returns the size of the bitmap when stored as a dense bitmap. Equals returns true if the two bitmaps contain the same integers Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed,
and any integer present in the range and not in the bitmap is added.
The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range
while uint64(0x100000000) cannot be represented as a 32-bit value. FlipInt calls Flip after casting the parameters (convenience method) Freeze serializes the bitmap in the CRoaring's frozen format. FreezeTo serializes the bitmap in the CRoaring's frozen format. FromBase64 deserializes a bitmap from Base64 FromBuffer creates a bitmap from its serialized version stored in buffer
The format specification is available here:
https://github.com/RoaringBitmap/RoaringFormatSpec
The provided byte array (buf) is expected to be a constant.
The function makes the best effort attempt not to copy data.
You should take care not to modify buff as it will
likely result in unexpected program behavior.
Resulting bitmaps are effectively immutable in the following sense:
a copy-on-write marker is used so that when you modify the resulting
bitmap, copies of selected data (containers) are made.
You should *not* change the copy-on-write status of the resulting
bitmaps (SetCopyOnWrite).
Thus FromBuffer is more likely to be appropriate for read-only use cases,
when the resulting bitmap can be considered immutable.
If buf becomes unavailable, then a bitmap created with
FromBuffer would be effectively broken. Furthermore, any
bitmap derived from this bitmap (e.g., via Or, And) might
also be broken. Thus, before making buf unavailable, you should
call CloneCopyOnWriteContainers on all such bitmaps.
See also the FromUnsafeBytes function which can have better performance
in some cases. FromDense unmarshalls from a slice of uint64s representing the bitmap as a dense bitmap.
Useful to convert bitmaps from libraries like https://github.com/bits-and-blooms/bitset or
https://github.com/kelindar/bitmap into roaring bitmaps fast and with convenience.
Callers are responsible for ensuring that the bitmap is empty before calling this function.
This function will not create any run containers, only array and bitmap containers. It is up to
the caller to call RunOptimize if they want to further compress the runs of consecutive values.
When doCopy is true, the bitmap is copied into a new slice for each bitmap container.
This is useful when the bitmap is going to be modified after this function returns or if it's
undesirable to hold references to large bitmaps which the GC would not be able to collect.
One copy can still happen even when doCopy is false if the bitmap length is not divisible
by bitmapContainerSize.
See FromBitSet. FromUnsafeBytes reads a serialized version of this bitmap from the byte buffer without copy.
It is the caller's responsibility to ensure that the input data is not modified and remains valid for the entire lifetime of this bitmap.
This method avoids small allocations but holds references to the input data buffer. It is GC-friendly, but it may consume more memory eventually.
The containers in the resulting bitmap are immutable containers tied to the provided byte array and they rely on
copy-on-write which means that modifying them creates copies. Thus FromUnsafeBytes is more likely to be appropriate for read-only use cases,
when the resulting bitmap can be considered immutable.
See also the FromBuffer function.
See https://github.com/RoaringBitmap/roaring/pull/395 for more details. FrozenView creates a static view of a serialized bitmap stored in buf.
It uses CRoaring's frozen bitmap format.
The format specification is available here:
https://github.com/RoaringBitmap/CRoaring/blob/2c867e9f9c9e2a3a7032791f94c4c7ae3013f6e0/src/roaring.c#L2756-L2783
The provided byte array (buf) is expected to be a constant.
The function makes the best effort attempt not to copy data.
Only little endian is supported. The function will err if it detects a big
endian serialized file.
You should take care not to modify buff as it will likely result in
unexpected program behavior.
If said buffer comes from a memory map, it's advisable to give it read
only permissions, either at creation or by calling Mprotect from the
golang.org/x/sys/unix package.
Resulting bitmaps are effectively immutable in the following sense:
a copy-on-write marker is used so that when you modify the resulting
bitmap, copies of selected data (containers) are made.
You should *not* change the copy-on-write status of the resulting
bitmaps (SetCopyOnWrite).
If buf becomes unavailable, then a bitmap created with
FromBuffer would be effectively broken. Furthermore, any
bitmap derived from this bitmap (e.g., via Or, And) might
also be broken. Thus, before making buf unavailable, you should
call CloneCopyOnWriteContainers on all such bitmaps. GetCardinality returns the number of integers contained in the bitmap GetCopyOnWrite gets this bitmap's copy-on-write property GetFrozenSizeInBytes returns the size in bytes of the frozen bitmap. GetSerializedSizeInBytes computes the serialized size in bytes
of the Bitmap. It should correspond to the
number of bytes written when invoking WriteTo. You can expect
that this function is much cheaper computationally than WriteTo. GetSizeInBytes estimates the memory usage of the Bitmap. Note that this
might differ slightly from the amount of bytes required for persistent storage HasRunCompression returns true if the bitmap benefits from run compression Intersects checks whether two bitmap intersects, bitmaps are not modified IntersectsWithInterval checks whether a bitmap 'rb' and an open interval '[x,y)' intersect. IsEmpty returns true if the Bitmap is empty (it is faster than doing (GetCardinality() == 0)) Iterate iterates over the bitmap, calling the given callback with each value in the bitmap. If the callback returns
false, the iteration is halted.
The iteration results are undefined if the bitmap is modified (e.g., with Add or Remove).
There is no guarantee as to what order the values will be iterated. Iterator creates a new IntPeekable to iterate over the integers contained in the bitmap, in sorted order;
the iterator becomes invalid if the bitmap is modified (e.g., with Add or Remove). ManyIterator creates a new ManyIntIterable to iterate over the integers contained in the bitmap, in sorted order;
the iterator becomes invalid if the bitmap is modified (e.g., with Add or Remove). MarshalBinary implements the encoding.BinaryMarshaler interface for the bitmap
(same as ToBytes) Maximum get the largest value stored in this roaring bitmap, assumes that it is not empty Minimum get the smallest value stored in this roaring bitmap, assumes that it is not empty Or computes the union between two bitmaps and stores the result in the current bitmap OrCardinality returns the cardinality of the union between two bitmaps, bitmaps are not modified Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality()).
If you pass the smallest value, you get the value 1. If you pass a value that is smaller than the smallest
value, you get 0. Note that this function differs in convention from the Select function since it
return 1 and not 0 on the smallest value. ReadFrom reads a serialized version of this bitmap from stream.
The format is compatible with other RoaringBitmap
implementations (Java, C) and is documented here:
https://github.com/RoaringBitmap/RoaringFormatSpec
Since io.Reader is regarded as a stream and cannot be read twice.
So add cookieHeader to accept the 4-byte data that has been read in roaring64.ReadFrom.
It is not necessary to pass cookieHeader when call roaring.ReadFrom to read the roaring32 data directly. Remove the integer x from the bitmap RemoveRange removes the integers in [rangeStart, rangeEnd) from the bitmap.
The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range
while uint64(0x100000000) cannot be represented as a 32-bit value. ReverseIterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order;
the iterator becomes invalid if the bitmap is modified (e.g., with Add or Remove). RunOptimize attempts to further compress the runs of consecutive values found in the bitmap Select returns the xth integer in the bitmap. If you pass 0, you get
the smallest element. Note that this function differs in convention from
the Rank function which returns 1 on the smallest value. SetCopyOnWrite sets this bitmap to use copy-on-write so that copies are fast and memory conscious
if the parameter is true, otherwise we leave the default where hard copies are made
(copy-on-write requires extra care in a threaded context).
Calling SetCopyOnWrite(true) on a bitmap created with FromBuffer is unsafe. Stats returns details on container type usage in a Statistics struct. String creates a string representation of the Bitmap ToArray creates a new slice containing all of the integers stored in the Bitmap in sorted order ToBase64 serializes a bitmap as Base64 ToBitSet copies the content of the RoaringBitmap into a bitset.BitSet instance ToBytes returns an array of bytes corresponding to what is written
when calling WriteTo ToDense returns a slice of uint64s representing the bitmap as a dense bitmap.
Useful to convert a roaring bitmap to a format that can be used by other libraries
like https://github.com/bits-and-blooms/bitset or https://github.com/kelindar/bitmap UnmarshalBinary implements the encoding.BinaryUnmarshaler interface for the bitmap WriteDenseTo writes to a slice of uint64s representing the bitmap as a dense bitmap.
Callers are responsible for allocating enough space in the bitmap using DenseSize.
Useful to convert a roaring bitmap to a format that can be used by other libraries
like https://github.com/bits-and-blooms/bitset or https://github.com/kelindar/bitmap WriteFrozenTo serializes the bitmap in the CRoaring's frozen format. WriteTo writes a serialized version of this bitmap to stream.
The format is compatible with other RoaringBitmap
implementations (Java, C) and is documented here:
https://github.com/RoaringBitmap/RoaringFormatSpec Xor computes the symmetric difference between two bitmaps and stores the result in the current bitmap
*Bitmap : github.com/gobwas/ws.HandshakeHeader
*Bitmap : encoding.BinaryMarshaler
*Bitmap : encoding.BinaryUnmarshaler
*Bitmap : expvar.Var
*Bitmap : fmt.Stringer
*Bitmap : io.WriterTo
func AddOffset(x *Bitmap, offset uint32) (answer *Bitmap)
func AddOffset64(x *Bitmap, offset int64) (answer *Bitmap)
func And(x1, x2 *Bitmap) *Bitmap
func AndNot(x1, x2 *Bitmap) *Bitmap
func BitmapOf(dat ...uint32) *Bitmap
func FastAnd(bitmaps ...*Bitmap) *Bitmap
func FastOr(bitmaps ...*Bitmap) *Bitmap
func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap
func FlipInt(bm *Bitmap, rangeStart, rangeEnd int) *Bitmap
func FromBitSet(bitset *bitset.BitSet) *Bitmap
func FromDense(bitmap []uint64, doCopy bool) *Bitmap
func HeapOr(bitmaps ...*Bitmap) *Bitmap
func HeapXor(bitmaps ...*Bitmap) *Bitmap
func New() *Bitmap
func NewBitmap() *Bitmap
func Or(x1, x2 *Bitmap) *Bitmap
func ParAnd(parallelism int, bitmaps ...*Bitmap) *Bitmap
func ParHeapOr(parallelism int, bitmaps ...*Bitmap) *Bitmap
func ParOr(parallelism int, bitmaps ...*Bitmap) *Bitmap
func Xor(x1, x2 *Bitmap) *Bitmap
func (*Bitmap).Clone() *Bitmap
func AddOffset(x *Bitmap, offset uint32) (answer *Bitmap)
func AddOffset64(x *Bitmap, offset int64) (answer *Bitmap)
func And(x1, x2 *Bitmap) *Bitmap
func AndNot(x1, x2 *Bitmap) *Bitmap
func FastAnd(bitmaps ...*Bitmap) *Bitmap
func FastOr(bitmaps ...*Bitmap) *Bitmap
func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap
func FlipInt(bm *Bitmap, rangeStart, rangeEnd int) *Bitmap
func HeapOr(bitmaps ...*Bitmap) *Bitmap
func HeapXor(bitmaps ...*Bitmap) *Bitmap
func Or(x1, x2 *Bitmap) *Bitmap
func ParAnd(parallelism int, bitmaps ...*Bitmap) *Bitmap
func ParHeapOr(parallelism int, bitmaps ...*Bitmap) *Bitmap
func ParOr(parallelism int, bitmaps ...*Bitmap) *Bitmap
func Xor(x1, x2 *Bitmap) *Bitmap
func (*Bitmap).And(x2 *Bitmap)
func (*Bitmap).AndAny(bitmaps ...*Bitmap)
func (*Bitmap).AndCardinality(x2 *Bitmap) uint64
func (*Bitmap).AndNot(x2 *Bitmap)
func (*Bitmap).Intersects(x2 *Bitmap) bool
func (*Bitmap).Or(x2 *Bitmap)
func (*Bitmap).OrCardinality(x2 *Bitmap) uint64
func (*Bitmap).Xor(x2 *Bitmap)
IntIterator is meant to allow you to iterate through the values of a bitmap, see Initialize(a *Bitmap) AdvanceIfNeeded advances as long as the next value is smaller than minval HasNext returns true if there are more integers to iterate over Initialize configures the existing iterator so that it can iterate through the values of
the provided bitmap.
The iteration results are undefined if the bitmap is modified (e.g., with Add or Remove). Next returns the next integer PeekNext peeks the next value without advancing the iterator
*IntIterator : IntIterable
*IntIterator : IntPeekable
IntPeekable allows you to look at the next value without advancing and
advance as long as the next value is smaller than minval AdvanceIfNeeded advances as long as the next value is smaller than minval( IntPeekable) HasNext() bool( IntPeekable) Next() uint32 PeekNext peeks the next value without advancing the iterator
IntPeekable : IntIterable
func (*Bitmap).Iterator() IntPeekable
IntReverseIterator is meant to allow you to iterate through the values of a bitmap, see Initialize(a *Bitmap) HasNext returns true if there are more integers to iterate over Initialize configures the existing iterator so that it can iterate through the values of
the provided bitmap.
The iteration results are undefined if the bitmap is modified (e.g., with Add or Remove). Next returns the next integer
*IntReverseIterator : IntIterable
ManyIntIterable allows you to iterate over the values in a Bitmap NextMany fills buf up with values, returns how many values were returned NextMany64 fills up buf with 64 bit values, uses hs as a mask (OR), returns how many values were returned
func (*Bitmap).ManyIterator() ManyIntIterable
ManyIntIterator is meant to allow you to iterate through the values of a bitmap, see Initialize(a *Bitmap) Initialize configures the existing iterator so that it can iterate through the values of
the provided bitmap.
The iteration results are undefined if the bitmap is modified (e.g., with Add or Remove).(*ManyIntIterator) NextMany(buf []uint32) int(*ManyIntIterator) NextMany64(hs64 uint64, buf []uint64) int
*ManyIntIterator : ManyIntIterable
AddOffset adds the value 'offset' to each and every value in a bitmap, generating a new bitmap in the process
AddOffset64 adds the value 'offset' to each and every value in a bitmap, generating a new bitmap in the process
If offset + element is outside of the range [0,2^32), that the element will be dropped
And computes the intersection between two bitmaps and returns the result
AndNot computes the difference between two bitmaps and returns the result
BitmapOf generates a new bitmap filled with the specified integers
BoundSerializedSizeInBytes returns an upper bound on the serialized size in bytes
assuming that one wants to store "cardinality" integers in [0, universe_size)
FastAnd computes the intersection between many bitmaps quickly
Compared to the And function, it can take many bitmaps as input, thus saving the trouble
of manually calling "And" many times.
Performance hints: if you have very large and tiny bitmaps,
it may be beneficial performance-wise to put a tiny bitmap
in first position.
FastOr computes the union between many bitmaps quickly, as opposed to having to call Or repeatedly.
It might also be faster than calling Or repeatedly.
Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed,
and any integer present in the range and not in the bitmap is added, a new bitmap is returned leaving
the current bitmap unchanged.
The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range
while uint64(0x100000000) cannot be represented as a 32-bit value.
FlipInt calls Flip after casting the parameters (convenience method)
FromBitSet creates a new RoaringBitmap from a bitset.BitSet instance
FromDense creates a bitmap from a slice of uint64s representing the bitmap as a dense bitmap.
Useful to convert bitmaps from libraries like https://github.com/bits-and-blooms/bitset or
https://github.com/kelindar/bitmap into roaring bitmaps fast and with convenience.
This function will not create any run containers, only array and bitmap containers. It's up to
the caller to call RunOptimize if they want to further compress the runs of consecutive values.
When doCopy is true, the bitmap is copied into a new slice for each bitmap container.
This is useful when the bitmap is going to be modified after this function returns or if it's
undesirable to hold references to large bitmaps which the GC would not be able to collect.
One copy can still happen even when doCopy is false if the bitmap length is not divisible
by bitmapContainerSize.
See also FromBitSet.
HeapOr computes the union between many bitmaps quickly using a heap.
It might be faster than calling Or repeatedly.
HeapXor computes the symmetric difference between many bitmaps quickly (as opposed to calling Xor repeated).
Internally, this function uses a heap.
It might be faster than calling Xor repeatedly.
New creates a new empty Bitmap (same as NewBitmap)
NewBitmap creates a new empty Bitmap (see also New)
Or computes the union between two bitmaps and returns the result
ParAnd computes the intersection (AND) of all provided bitmaps in parallel,
where the parameter "parallelism" determines how many workers are to be used
(if it is set to 0, a default number of workers is chosen)
ParHeapOr computes the union (OR) of all provided bitmaps in parallel,
where the parameter "parallelism" determines how many workers are to be used
(if it is set to 0, a default number of workers is chosen)
ParHeapOr uses a heap to compute the union. For rare cases it might be faster than ParOr
ParOr computes the union (OR) of all provided bitmaps in parallel,
where the parameter "parallelism" determines how many workers are to be used
(if it is set to 0, a default number of workers is chosen)
Xor computes the symmetric difference between two bitmaps and returns the result
Package-Level Variables (total 7)
ErrFrozenBitmapBigEndian is returned when the header is big endian.
ErrFrozenBitmapBufferTooSmall is returned when the buffer is too small.
ErrFrozenBitmapIncomplete is returned when the buffer is too small to contain a frozen bitmap.
ErrFrozenBitmapInvalidCookie is returned when the header does not contain the frozenCookie.
ErrFrozenBitmapInvalidTypecode is returned when the typecode is invalid.
ErrFrozenBitmapOverpopulated is returned when the number of containers is too large.
ErrFrozenBitmapUnexpectedData is returned when the buffer contains unexpected data.
Package-Level Constants (total 3)
MaxRange is One more than the maximum allowed bitmap bit index. For use as an upper
bound for ranges.
MaxUint16 is the largest 16 bit unsigned int.
This is the largest value an interval16 can store.
MaxUint32 is the largest uint32 value.
The pages are generated with Goldsv0.8.2. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @zigo_101 (reachable from the left QR code) to get the latest news of Golds.
